package org.example.myleet.p911;

public class TopVotedCandidate {

    private int[] timeWin;

    private int[] times;

    /**
     * 哈希表记录对应时间点获胜的候选人
     */
    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        int n = persons.length;
        timeWin = new int[n];
        int[] votes = new int[n];
        int winCandidate = votes[0];
        for (int i = 0; i < n; ++i) {
            ++votes[persons[i]];
            if (votes[persons[i]] >= votes[winCandidate]) {
                //题目要求平局情况下最新获得选票的人获胜，用>=
                winCandidate = persons[i];
            }
            timeWin[i] = winCandidate;
        }
    }

    /**
     * 二分法快速找到对应的时间点，直接查询该时间节点下获胜的人
     */
    public int q(int t) {
        int l = 0, r = times.length - 1, m = 0;
        while (r - l > 1) {
            m = (r + l) / 2;
            if (times[m] > t) {
                r = m;
            } else if (times[m] < t) {
                l = m;
            } else {
                break;
            }
        }
        int time = m;
        if (times[m] != t) {
            if (times[r] <= t) {
                time = r;
            } else {
                time = l;
            }
        }
        return timeWin[time];
    }
}
